{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Disconnect Path in a Binary Matrix by at Most One Flip"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPossibleToCutPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制矩阵中翻转最多一次使路径不连通"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的&nbsp;<code>m x n</code>&nbsp;<strong>二进制</strong> 矩阵&nbsp;<code>grid</code>&nbsp;。你可以从一个格子&nbsp;<code>(row, col)</code>&nbsp;移动到格子&nbsp;<code>(row + 1, col)</code>&nbsp;或者&nbsp;<code>(row, col + 1)</code>&nbsp;，前提是前往的格子值为 <code>1</code>&nbsp;。如果从&nbsp;<code>(0, 0)</code>&nbsp;到&nbsp;<code>(m - 1, n - 1)</code>&nbsp;没有任何路径，我们称该矩阵是&nbsp;<strong>不连通</strong>&nbsp;的。</p>\n",
    "\n",
    "<p>你可以翻转 <strong>最多一个</strong>&nbsp;格子的值（也可以不翻转）。你 <strong>不能翻转</strong>&nbsp;格子&nbsp;<code>(0, 0)</code> 和&nbsp;<code>(m - 1, n - 1)</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果可以使矩阵不连通，请你返回&nbsp;<code>true</code>&nbsp;，否则返回<em>&nbsp;</em><code>false</code><em>&nbsp;</em>。</p>\n",
    "\n",
    "<p><strong>注意</strong>&nbsp;，翻转一个格子的值，可以使它的值从&nbsp;<code>0</code>&nbsp;变&nbsp;<code>1</code>&nbsp;，或从&nbsp;<code>1</code>&nbsp;变&nbsp;<code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/07/yetgrid2drawio.png\" style=\"width: 441px; height: 151px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1,1,1],[1,0,0],[1,1,1]]\n",
    "<strong>输出：</strong>true\n",
    "<b>解释：</b>按照上图所示我们翻转蓝色格子里的值，翻转后从 (0, 0) 到 (2, 2) 没有路径。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/07/yetgrid3drawio.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1,1,1],[1,0,1],[1,1,1]]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>无法翻转至多一个格子，使 (0, 0) 到 (2, 2) 没有路径。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>grid[0][0] == grid[m - 1][n - 1] == 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [disconnect-path-in-a-binary-matrix-by-at-most-one-flip](https://leetcode.cn/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [disconnect-path-in-a-binary-matrix-by-at-most-one-flip](https://leetcode.cn/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,0,0],[1,1,1]]', '[[1,1,1],[1,0,1],[1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0: continue\n",
    "                if i:\n",
    "                    dp[i][j] |= dp[i - 1][j]\n",
    "                if j:\n",
    "                    dp[i][j] |= dp[i][j - 1]\n",
    "        if not dp[m - 1][n - 1]:\n",
    "            return True\n",
    "        q = set([(m - 1, n - 1)])\n",
    "        while q:\n",
    "            # print(q)\n",
    "            ne = set()\n",
    "            for x, y in q:\n",
    "                for dx, dy in [(-1, 0), (0, -1)]:\n",
    "                    if 0 <= x + dx < m and 0 <= y + dy < n and dp[x + dx][y + dy]:\n",
    "                        ne.add((x + dx, y + dy))\n",
    "            # print(ne)\n",
    "            if len(ne) == 1 and (0, 0) not in ne:\n",
    "                return True\n",
    "            q = ne\n",
    "        return False\n",
    "            \n",
    "        # print(dp[m - 1][n - 1])\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def walk():\n",
    "            lastRow = [0]*n\n",
    "            lastRow[0] = 1\n",
    "            for r, row in enumerate(grid):\n",
    "                last = 0\n",
    "                for c, (lv, v) in enumerate(zip(lastRow, row)):\n",
    "                    if v:\n",
    "                        if (last or lv):\n",
    "                            v = row[c] = 2 if last else 3\n",
    "                        else: \n",
    "                            v = row[c] = 0\n",
    "                    last = v\n",
    "                lastRow = row\n",
    "        walk()\n",
    "        if grid[-1][-1] < 2: return True\n",
    "        r, c = m - 1, n - 1\n",
    "        while r or c:\n",
    "            v = grid[r][c]\n",
    "            grid[r][c] = 0\n",
    "            if v == 2:\n",
    "                c -= 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        grid[-1][-1] = 1\n",
    "        walk()\n",
    "        return grid[-1][-1] < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reach(self, x: int, y: int, grid: List[List[int]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        if x == n - 1 and y == m - 1:\n",
    "            return True\n",
    "        grid[x][y] = 0\n",
    "        x1, y1 = x, y + 1\n",
    "        if y1 < m and grid[x1][y1] == 1:\n",
    "            ret = self.reach(x1, y1, grid)\n",
    "            if ret:\n",
    "                return ret\n",
    "        x2, y2 = x + 1, y\n",
    "        if x2 < n and grid[x2][y2] == 1:\n",
    "            return self.reach(x2, y2, grid)\n",
    "        return False\n",
    "    \n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        if not self.reach(0, 0, grid):\n",
    "            return True\n",
    "        grid[0][0], grid[n - 1][m - 1] = 1, 1\n",
    "        if not self.reach(0, 0, grid):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_path(self, grid, start):\n",
    "        if start[0] == (len(grid) - 1) and start[1] == (len(grid[0]) - 1):\n",
    "            return True\n",
    "        self.grid[start[0]][start[1]] = 0\n",
    "\n",
    "        if start[0] < (len(grid) - 1) and self.grid[start[0] + 1][start[1]] and self.get_path(self.grid, [start[0] + 1, start[1]]):\n",
    "                return True\n",
    "        \n",
    "        if start[1] < (len(grid[0]) - 1) and self.grid[start[0]][start[1] + 1] and self.get_path(self.grid, [start[0], start[1] + 1]):\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        self.grid = grid\n",
    "\n",
    "        return  not (self.get_path(self.grid, [0,0]) and self.get_path(self.grid, [0,0]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 先下后右 \n",
    "    # 先右后下\n",
    "    # 最大限度可以使2条路不相交\n",
    "    # dfs两个\n",
    "    def dfs_l_r(self, x, y):\n",
    "        if x < self.m-1 and self.grid[x+1][y] == 1:\n",
    "            path = self.dfs_l_r(x+1, y)\n",
    "            if path:\n",
    "                return str(x) +','+ str(y) +'|'+ path\n",
    "            \n",
    "        if y < self.n-1 and self.grid[x][y+1] == 1:\n",
    "            path2 = self.dfs_l_r(x, y+1)\n",
    "            if path2:\n",
    "                return str(x) +','+ str(y) +'|'+ path2\n",
    "\n",
    "            \n",
    "        if x==self.m-1 and y==self.n-1: \n",
    "            return str(x) +','+ str(y)\n",
    "        \n",
    "        return False\n",
    "\n",
    "    def dfs_r_l(self, x, y):\n",
    "        if x==self.m-1 and y==self.n-1: \n",
    "            return str(x) +','+ str(y)\n",
    "        \n",
    "        if y < self.n-1 and self.grid[x][y+1] == 1:\n",
    "            path = self.dfs_r_l(x, y+1)\n",
    "            if path:\n",
    "                return str(x) +','+ str(y) +'|'+ path\n",
    "        \n",
    "        if x < self.m-1 and self.grid[x+1][y] == 1:\n",
    "            path2 = self.dfs_r_l(x+1, y)\n",
    "            if path2:\n",
    "                return str(x) +','+ str(y) +'|'+ path2\n",
    "        \n",
    "        return False\n",
    "\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        self.m = len(grid)\n",
    "        self.n = len(grid[0])\n",
    "        self.grid = grid\n",
    "        self.path_str = []\n",
    "        result1 = self.dfs_l_r(0,0)\n",
    "        result2 = self.dfs_r_l(0,0)\n",
    "        # print(result1, result2)\n",
    "        if result1 and result2:\n",
    "            p1 = set(result1.split('|')[1:-1])\n",
    "            p2 = set(result2.split('|')[1:-1])\n",
    "            # 没有相同的 False\n",
    "            if not p1 & p2:\n",
    "                return False\n",
    "        return True\n",
    "        # 如果本身不连通 只有一条路可以连通 所有路有同一个必经点 True\n",
    "        # 能找出两条完全不重合的路 False# 贪心 一直右 一直下 // 一直下 再一直向右\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(x, y):\n",
    "            if x == m- 1 and y == n-1:\n",
    "                return True\n",
    "            grid[x][y] = 0\n",
    "            return x < m - 1 and grid[x+1][y] and dfs(x+1, y) or \\\n",
    "                    y < n - 1 and grid[x][y+1] and dfs(x, y+1)\n",
    "        return not dfs(0, 0) or not dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        def dfs(i,j):\n",
    "            if i==len(grid)-1 and j==len(grid[0])-1:\n",
    "                return True\n",
    "            grid[i][j]=0\n",
    "            return (i<len(grid)-1 and grid[i+1][j] and dfs(i+1,j)) or (j<len(grid[0])-1 and grid[i][j+1] and dfs(i,j+1))\n",
    "        return not dfs(0,0) or not dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return True\n",
    "            grid[i][j] = 0\n",
    "            return i < m - 1 and grid[i + 1][j] and dfs(i + 1, j) or j < n - 1 and grid[i][j + 1] and dfs(i, j + 1)\n",
    "        return not dfs(0, 0) or not dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if x == m-1 and y == n-1: return True\n",
    "            grid[x][y] = 0\n",
    "            return x < m-1 and grid[x+1][y] and dfs(x+1, y) or\\\n",
    "                    y < n-1 and grid[x][y+1] and dfs(x, y+1)\n",
    "        return not dfs(0, 0) or not dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        m, n = len(g), len(g[0])\n",
    "        def dfs(x: int, y: int) -> bool:  # 返回能否到达终点\n",
    "            if x == m - 1 and y == n - 1: return True\n",
    "            g[x][y] = 0  # 直接修改\n",
    "            return x < m - 1 and g[x + 1][y] and dfs(x + 1, y) or \\\n",
    "                   y < n - 1 and g[x][y + 1] and dfs(x, y + 1)\n",
    "        return not dfs(0, 0) or not dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def dfs(x:int, y:int)->bool:\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            grid[x][y]=0\n",
    "            return x<m-1 and grid[x+1][y] and dfs(x+1,y) or \\\n",
    "                   y<n-1 and grid[x][y+1] and dfs(x,y+1)\n",
    "\n",
    "        return not dfs(0,0) or not dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return True\n",
    "            grid[x][y] = 0\n",
    "            \n",
    "            return x + 1 < m and grid[x + 1][y] and dfs(x + 1, y) or \\\n",
    "                   y + 1 < n and grid[x][y + 1] and dfs(x, y + 1)\n",
    "        \n",
    "        return not dfs(0, 0) or not dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        m, n = len(g), len(g[0])\n",
    "        def dfs(x: int, y: int) -> bool:  # 返回能否到达终点\n",
    "            if x == m - 1 and y == n - 1: return True\n",
    "            g[x][y] = 0  # 直接修改\n",
    "            return x < m - 1 and g[x + 1][y] and dfs(x + 1, y) or \\\n",
    "                   y < n - 1 and g[x][y + 1] and dfs(x, y + 1)\n",
    "        return not dfs(0, 0) or not dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        # dfs遍历路径，将任意一条路径上的1修改为0，如果没有其他路径能够达到右下角的点，则返回TRUE\n",
    "        m,n=len(g),len(g[0])\n",
    "        def dfs(x,y):\n",
    "            # 结束条件，如果能达到则返回True\n",
    "            if x==m-1 and y==n-1: return True \n",
    "            g[x][y]=0\n",
    "            if (x+1<m and g[x+1][y]==1 and dfs(x+1,y)) or (y+1<n and g[x][y+1]==1 and dfs(x,y+1)):\n",
    "                return True \n",
    "            return False\n",
    "        return  (not dfs(0,0)) or (not dfs(0,0))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        m, n = len(g), len(g[0])\n",
    "        \n",
    "        def dfs(x: int, y: int) -> bool:  # 返回能否到达终点\n",
    "            if x == m - 1 and y == n - 1: \n",
    "                return True\n",
    "            g[x][y] = 0  # 直接修改，以避免重复访问\n",
    "            return x < m - 1 and g[x + 1][y] and dfs(x + 1, y) or \\\n",
    "                   y < n - 1 and g[x][y + 1] and dfs(x, y + 1)\n",
    "\n",
    "        # 先判断原始矩阵是否连通\n",
    "        # 如果连通，再次调用DFS判断在修改访问标记后是否还连通\n",
    "        return not dfs(0, 0) or not dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        find=False\n",
    "        def dfs(x,y):\n",
    "            nonlocal find\n",
    "            if find:\n",
    "                return\n",
    "            if x==m-1 and y==n-1:\n",
    "                find =True\n",
    "                return\n",
    "            if x>=m or y>=n or x<0 or y<0:\n",
    "                return  \n",
    "            if grid[x][y]==0:\n",
    "                return \n",
    "            grid[x][y]=0\n",
    "            dfs(x+1,y)\n",
    "            dfs(x,y+1)\n",
    "        dfs(0,0)\n",
    "        grid[0][0]=1\n",
    "        find=False\n",
    "        def dfs2(x,y):\n",
    "            nonlocal find\n",
    "            if find:\n",
    "                return\n",
    "            if x==m-1 and y==n-1:\n",
    "                find =True\n",
    "                return\n",
    "            if x>=m or y>=n or x<0 or y<0:\n",
    "                return  \n",
    "            if grid[x][y]==0:\n",
    "                return \n",
    "            grid[x][y]=0\n",
    "            dfs2(x,y+1)\n",
    "            dfs2(x+1,y)\n",
    "        dfs2(0,0)\n",
    "        return not find "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        m,n = len(g),len(g[0])\n",
    "        def dfs(x:int,y:int) -> bool:\n",
    "            if x == m-1 and y == n - 1: return True\n",
    "            g[x][y] = 0\n",
    "            return x< m-1 and g[x+1][y] and dfs(x+1,y) or \\\n",
    "                y< n- 1 and g[x][y+1] and dfs(x,y+1)\n",
    "        return not dfs(0,0) or not dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        '''\n",
    "        找到两个并查集之间，唯一联通的边\n",
    "        翻转从0到1，只会使矩阵更可能联通\n",
    "        所以应该反转1到0\n",
    "\n",
    "        研究从起点到终点的路径条数，如果仅有1条，就是可以通过翻转来变为不联通\n",
    "        如果有多条，\n",
    "        所有路径都重复经过了某一个点：可以使矩阵不连通\n",
    "        否则，不可能只翻转一次来使矩阵变得不连通\n",
    "\n",
    "        随便找到一条路径(dfs),然后把路径上的点mark掉，看看还能不能找到一条新的路径即可\n",
    "        更进一步地，转换成求轮廓是否有交集\n",
    "\n",
    "        '''\n",
    "        m=len(g)\n",
    "        n=len(g[0])\n",
    "        def dfs(x:int,y:int)->bool:\n",
    "            if x==m-1 and y==n-1:return True\n",
    "            g[x][y]=0\n",
    "            return x<m-1 and g[x+1][y] and dfs(x+1,y) or\\\n",
    "            y<n-1 and g[x][y+1] and dfs(x,y+1)\n",
    "        return not dfs(0,0) or not dfs(0,0)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        m, n = len(g), len(g[0])\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            if x == m - 1 and y == n - 1: return True\n",
    "            g[x][y] = 0\n",
    "            return x < m - 1 and g[x + 1][y] and dfs(x + 1, y) or \\\n",
    "                   y < n - 1 and g[x][y + 1] and dfs(x, y + 1)\n",
    "        return not dfs(0, 0) or not dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        m, n = len(g), len(g[0])\n",
    "        def dfs(x: int, y: int) -> bool:  # 返回能否到达终点\n",
    "            if x == m - 1 and y == n - 1: return True\n",
    "            g[x][y] = 0  # 直接修改\n",
    "            return x < m - 1 and g[x + 1][y] and dfs(x + 1, y) or \\\n",
    "                   y < n - 1 and g[x][y + 1] and dfs(x, y + 1)\n",
    "        return not dfs(0, 0) or not dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, g: List[List[int]]) -> bool:\n",
    "        # dfs遍历路径，将任意一条路径上的1修改为0，如果没有其他路径能够达到右下角的点，则返回TRUE\n",
    "        m,n=len(g),len(g[0])\n",
    "        def dfs(x,y):\n",
    "            # 结束条件，如果能达到则返回True\n",
    "            if x==m-1 and y==n-1: return True \n",
    "            g[x][y]=0\n",
    "            if (x+1<m and g[x+1][y]==1 and dfs(x+1,y)) or (y+1<n and g[x][y+1]==1 and dfs(x,y+1)):\n",
    "                return True \n",
    "            return False\n",
    "        return not dfs(0,0) or not dfs(0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        def dfs(x,y):\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            grid[x][y]=0\n",
    "            return (x+1<m and grid[x+1][y] and dfs(x+1,y)) or (y+1<n and grid[x][y+1] and dfs(x, y+1))\n",
    "        return not dfs(0,0) or not dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath1(self, grid: List[List[int]]) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        if grid[0][0]==1:\n",
    "            dp[0][0]=1\n",
    "        for i in range(1,m):\n",
    "            if grid[i][0]==1:\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "            else:\n",
    "                break\n",
    "        for i in range(1, n):\n",
    "            if grid[0][i]==1:\n",
    "                dp[0][i]=dp[0][i-1]\n",
    "            else:\n",
    "                break\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j]==1:\n",
    "                    dp[i][j]=dp[i-1][j]+dp[i][j-1]\n",
    "        return dp[m-1][n-1]<2\n",
    "\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def dfs(x, y):\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            grid[x][y]=0\n",
    "            return (x<m-1 and grid[x+1][y] and dfs(x+1, y)) or (y<n-1 and grid[x][y+1] and dfs(x, y+1))\n",
    "        return not dfs(0,0) or not dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# class UnionFind:\n",
    "#     def __init__(self, n: int) -> None:\n",
    "#         self.parent = list(range(n))\n",
    "#         self.n = n\n",
    "\n",
    "#     def find(self, x: int) -> int:\n",
    "#         if(self.parent[x] != x):\n",
    "#             self.parent[x] = self.find(self.parent[x])\n",
    "#         return self.parent[x]\n",
    "\n",
    "#     def union(self, x: int, y: int) -> None:\n",
    "#         rootX = self.find(x)\n",
    "#         rootY = self.find(y)\n",
    "#         if(rootX == rootY):\n",
    "#             return\n",
    "        \n",
    "#         self.parent[rootX] = rootY\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if(n==1 and m == 1):\n",
    "            return False\n",
    "        dirs = [(1,0),(0,1)]\n",
    "\n",
    "        st = set()\n",
    "        mp = dict()\n",
    "        def dfs(x:int, y:int) -> bool:\n",
    "            nonlocal mp, st\n",
    "            if(x == n-1 and y == m-1):\n",
    "                return True\n",
    "\n",
    "            for x0, y0 in dirs:\n",
    "                nx = x + x0\n",
    "                ny = y + y0\n",
    "\n",
    "                if(nx < 0 or ny < 0 or nx >= n or ny >= m):\n",
    "                    continue\n",
    "                if((nx, ny) in st):\n",
    "                    continue\n",
    "                if(grid[nx][ny] != 1):\n",
    "                    continue\n",
    "                mp[(nx, ny)] = (x, y)\n",
    "                st.add((nx, ny))\n",
    "                if(dfs(nx, ny)):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        if(not dfs(0,0)):\n",
    "            return True\n",
    "\n",
    "\n",
    "        x, y = n-1, m-1\n",
    "        st.clear()\n",
    "        while(x != 0 or y != 0):\n",
    "            x, y = mp[(x,y)]\n",
    "            st.add((x,y))\n",
    "        st.remove((0,0))\n",
    "\n",
    "        # print(\"enter dfs2 \", st)\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        def dfs2(x:int, y:int) -> bool:\n",
    "            nonlocal mp, st\n",
    "            if(x == n-1 and y == m-1):\n",
    "                return True\n",
    "\n",
    "            for x0, y0 in dirs:\n",
    "                nx = x + x0\n",
    "                ny = y + y0\n",
    "\n",
    "                if(nx < 0 or ny < 0 or nx >= n or ny >= m):\n",
    "                    continue\n",
    "                if((nx, ny) in visited or (nx, ny) in st):\n",
    "                    continue\n",
    "                if(grid[nx][ny] != 1):\n",
    "                    continue\n",
    "                visited.add((nx, ny))\n",
    "                if(dfs2(nx, ny)):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return not dfs2(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid) - 1, len(grid[0]) - 1\n",
    "        if m == 0 or n == 0:\n",
    "            return m + n > 1\n",
    "        if not all(grid[i][j] for i, j in ((1, 0), (0, 1), (m - 1, n), (m, n - 1))):\n",
    "            return True\n",
    "        for i, j in ((0, 0), (m, n), (0, 1), (1, 0)):\n",
    "            grid[i][j] = 0\n",
    "        s, a = set(), (m, n - 1)\n",
    "        \n",
    "        def f(t):\n",
    "            if t == a:\n",
    "                return True\n",
    "            i, j = t\n",
    "            for i1, j1 in ((i + 1, j), (i, j + 1)):\n",
    "                if i1 <= m and j1 <= n and grid[i1][j1]:\n",
    "                    t = (i1, j1)\n",
    "                    if t in s:\n",
    "                        continue\n",
    "                    s.add(t)\n",
    "                    if f(t):\n",
    "                        grid[i1][j1] = 0\n",
    "                        return True\n",
    "            \n",
    "        if not f((1, 0)):\n",
    "            return True\n",
    "        s.clear()\n",
    "        a = (m - 1, n)\n",
    "        return not f((0, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid) - 1, len(grid[0]) - 1\n",
    "        if m == 0 or n == 0:\n",
    "            return m + n > 1\n",
    "        if not all(grid[i][j] for i, j in ((1, 0), (0, 1), (m - 1, n), (m, n - 1))):\n",
    "            return True\n",
    "        for i, j in ((0, 0), (m, n), (0, 1), (1, 0)):\n",
    "            grid[i][j] = 0\n",
    "        s, a = set(), (m, n - 1)\n",
    "        \n",
    "        def f(t):\n",
    "            if t == a:\n",
    "                return True\n",
    "            i, j = t\n",
    "            for i1, j1 in ((i + 1, j), (i, j + 1)):\n",
    "                if 0 <= i1 <= m and 0 <= j1 <= n and grid[i1][j1]:\n",
    "                    t = (i1, j1)\n",
    "                    if t in s:\n",
    "                        continue\n",
    "                    s.add(t)\n",
    "                    if f(t):\n",
    "                        grid[i1][j1] = 0\n",
    "                        return True\n",
    "            \n",
    "        if not f((1, 0)):\n",
    "            return True\n",
    "        s.clear()\n",
    "        a = (m - 1, n)\n",
    "        return not f((0, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        def dfs(x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return True\n",
    "            grid[x][y] = 0\n",
    "            ans = False\n",
    "            for d in [[0, 1], [1, 0]]:\n",
    "                nx, ny = x + d[0], y + d[1]\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "                    continue\n",
    "                if not grid[nx][ny]:\n",
    "                    continue\n",
    "                ans = ans or dfs(nx, ny)\n",
    "            return ans\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if not grid[0][0] or not grid[m - 1][n - 1]:\n",
    "            return True\n",
    "        return not dfs(0, 0) or not dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 or n == 1:\n",
    "            return m + n > 3\n",
    "        if not all(grid[i][j] for i, j in ((1, 0), (0, 1), (-2, -1), (-1, -2))):\n",
    "            return True\n",
    "        for i, j in ((0, 0), (-1, -1), (0, 1), (1, 0)):\n",
    "            grid[i][j] = 0\n",
    "        s, a = set(), (m - 1, n - 2)\n",
    "        \n",
    "        def f(t):\n",
    "            if t == a:\n",
    "                return True\n",
    "            i, j = t\n",
    "            for i1, j1 in ((i + 1, j), (i, j + 1)):\n",
    "                if i1 < m and j1 < n and grid[i1][j1]:\n",
    "                    t = (i1, j1)\n",
    "                    if t in s:\n",
    "                        continue\n",
    "                    s.add(t)\n",
    "                    if f(t):\n",
    "                        grid[i1][j1] = 0\n",
    "                        return True\n",
    "            \n",
    "        if not f((1, 0)):\n",
    "            return True\n",
    "        s.clear()\n",
    "        a = (m - 2, n - 1)\n",
    "        return grid[-2][-1] == 0 or not f((0, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        vis=set()\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if m==1 and n==2:\n",
    "            return False\n",
    "        if m==2 and n==1:\n",
    "            return False\n",
    "        if m==1 and n==1:\n",
    "            return False\n",
    "        if m==1 or n==1:\n",
    "            return True\n",
    "        \n",
    "        #grid[0][1]=0\n",
    "\n",
    "        stack=[]\n",
    "        f=0\n",
    "        stack.append([0,0])\n",
    "        vis.add((0,0))\n",
    "        #print(m-1,n-1)\n",
    "       # return True\n",
    "        nexstack=[]\n",
    "        def dfs(x,y):\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            grid[x][y]=0\n",
    "         \n",
    "            for x1,y1 in [[x+1,y],[x,y+1]]:\n",
    "                if 0<=x1<m and 0<=y1<n and grid[x1][y1]==1:\n",
    "                    if dfs(x1,y1):\n",
    "                        return True\n",
    "        \n",
    "\n",
    "    \n",
    "        return not dfs(0,0) or not dfs(0,0)\n",
    "    \n",
    "       # return False\n",
    "\n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        vis=set()\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if m==1 and n==2:\n",
    "            return False\n",
    "        if m==2 and n==1:\n",
    "            return False\n",
    "        if m==1 and n==1:\n",
    "            return False\n",
    "        if m==1 or n==1:\n",
    "            return True\n",
    "        \n",
    "        #grid[0][1]=0\n",
    "\n",
    "        stack=[]\n",
    "        f=0\n",
    "        stack.append([0,0])\n",
    "        vis.add((0,0))\n",
    "        #print(m-1,n-1)\n",
    "       # return True\n",
    "  \n",
    "        def dfs(x,y):\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            grid[x][y]=0\n",
    "         \n",
    "            for x1,y1 in [[x+1,y],[x,y+1]]:\n",
    "                if 0<=x1<m and 0<=y1<n and grid[x1][y1]==1:\n",
    "                    if dfs(x1,y1):\n",
    "                        return True\n",
    "        \n",
    "            return False\n",
    "    \n",
    "        return not dfs(0,0) or not dfs(0,0)\n",
    "    \n",
    "       # return False\n",
    "\n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ll=[[0,1],[1,0]]\n",
    "        \n",
    "        \n",
    "        visited1=set()\n",
    "        \n",
    "        \n",
    "        def dfs1(i,j):\n",
    "            visited1.add((i,j))\n",
    "            if i==m-1 and j==n-1:\n",
    "                return True\n",
    "            \n",
    "            \n",
    "            for ii,jj in ll:\n",
    "                newi,newj=i+ii,j+jj\n",
    "                if 0<=newi<m and 0<=newj<n and grid[newi][newj] and (newi,newj) not in visited1:\n",
    "                    temp=dfs1(newi,newj)\n",
    "                    if temp:return True\n",
    "                    \n",
    "            return False\n",
    "                \n",
    "                \n",
    "        if not dfs1(0,0):return True\n",
    "        \n",
    "        \n",
    "        \n",
    "        ll=[[1,0],[0,1]]\n",
    "        visited2=set()\n",
    "        def dfs2(i,j):\n",
    "            visited2.add((i,j))\n",
    "            if i==m-1 and j==n-1:\n",
    "                return True\n",
    "            \n",
    "            for ii,jj in ll:\n",
    "                newi,newj=i+ii,j+jj\n",
    "                if 0<=newi<m and 0<=newj<n and grid[newi][newj] and (newi,newj) not in visited2:\n",
    "                    if dfs2(newi,newj):return True\n",
    "                    \n",
    "            return False\n",
    "                \n",
    "                \n",
    "        dfs2(0,0)\n",
    "        \n",
    "        # print(visited1)\n",
    "        # print(visited2)\n",
    "        \n",
    "        for i in visited1:\n",
    "            if i==(0,0) or i==(m-1,n-1):continue\n",
    "            if i in visited2:\n",
    "                return True\n",
    "            \n",
    "        return False\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        down,up,two = [ [False for _ in range(n)] for _ in range(m)], [ [False for _ in range(n)] for _ in range(m)], [ [False for _ in range(n)] for _ in range(m)]\n",
    "        visited = [ [False for _ in range(n)] for _ in range(m)]\n",
    "        q = queue.Queue()\n",
    "        q.put([0,0])\n",
    "        print(m,n)\n",
    "        while not q.empty():\n",
    "            i,j = q.get()\n",
    "            # print(i,j)\n",
    "            down[i][j] = True\n",
    "            if i+1<m and grid[i+1][j]==1 and not visited[i+1][j]:\n",
    "                q.put([i+1,j])\n",
    "                visited[i + 1][j]= True\n",
    "            if j+1<n and grid[i][j+1]==1 and not visited[i][j+1]:\n",
    "                q.put([i,j+1])\n",
    "                visited[i][j + 1] = True\n",
    "\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        q = queue.Queue()\n",
    "        q.put([m-1, n-1])\n",
    "        while not q.empty():\n",
    "            i,j = q.get()\n",
    "            up[i][j] = True\n",
    "            if i-1>=0 and grid[i-1][j]==1 and not visited[i-1][j]:\n",
    "                visited[i - 1][j] = True\n",
    "                q.put([i-1,j])\n",
    "            if j-1>=0 and grid[i][j-1]==1 and not visited[i][j-1]:\n",
    "                visited[i][j - 1]=True\n",
    "                q.put([i,j-1])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                two[i][j] = down[i][j] and up[i][j]\n",
    "\n",
    "        # print('down',down)\n",
    "        # print('up',up)\n",
    "        # print('two',two)\n",
    "        if not two[m-1][n-1]:\n",
    "            return True\n",
    "        count=0\n",
    "\n",
    "        q = queue.Queue()\n",
    "        q.put([0, 0])\n",
    "        two[0][0]=False\n",
    "        while not q.empty():\n",
    "            i, j = q.get()\n",
    "            # print('最后')\n",
    "            if i - 1 >= 0 and two[i - 1][j]:\n",
    "                two[i-1][j]=False\n",
    "                q.put([i - 1, j])\n",
    "            if j - 1 >= 0 and two[i][j - 1]:\n",
    "                q.put([i, j - 1])\n",
    "                two[i][j-1]=False\n",
    "            if i+1<m and two[i+1][j]:\n",
    "                q.put([i+1,j])\n",
    "                two[i+1][j]=False\n",
    "            if j+1<n and two[i][j+1]:\n",
    "                q.put([i,j+1])\n",
    "                two[i][j+1]=False\n",
    "            # print(q.queue, len(q.queue))\n",
    "            if len(q.queue)==1:\n",
    "                if q.queue[0]==[m-1,n-1]:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "      ok=0\n",
    "      ok1=0\n",
    "      f1,f2,=Counter(),Counter() \n",
    "      n=len(grid)\n",
    "      m=len(grid[0])  \n",
    "      def q(x,y):\n",
    "         return x*m+y\n",
    "      def k(x,y):\n",
    "         return 0<=x<n and 0<=y<m\n",
    "      def g(i,j):\n",
    "         nonlocal ok,ok1\n",
    "         if i==n-1 and j==m-1:\n",
    "            ok=1\n",
    "            ok1=1\n",
    "            return \n",
    "         for a,b in [[1,0],[0,1]]:\n",
    "           x=i+a\n",
    "           y=j+b\n",
    "           if k(x,y) and grid[x][y]:\n",
    "              if q(x,y) not in f1:\n",
    "                 f1[q(x,y)]+=1\n",
    "              else:\n",
    "                 f1[q(x,y)]+=1     \n",
    "              g(x,y)\n",
    "              if ok: \n",
    "                 return\n",
    "              f1[q(x,y)]-=1\n",
    "      def g1(i,j):\n",
    "        nonlocal ok,ok1 \n",
    "        if i==n-1 and j==m-1:\n",
    "            ok=1 \n",
    "            return \n",
    "        for a,b in [[0,1],[1,0]]:\n",
    "           x=i+a\n",
    "           y=j+b\n",
    "           if k(x,y) and grid[x][y]:\n",
    "               \n",
    "               f2[q(x,y)]+=1\n",
    "               g1(x,y)\n",
    "               if ok:\n",
    "                   return\n",
    "               f2[q(x,y)]-=1\n",
    "      ok=0\n",
    "      g(0,0)\n",
    "      ok=0\n",
    "      g1(0,0)\n",
    "      if not ok1:\n",
    "            return True\n",
    "      print(f1,f2)      \n",
    "      for x in f2:\n",
    "         if x != (n-1)*m+m-1 and x in f1 and f1[x]>=1:\n",
    "               return True\n",
    "      return False              \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        ok,ok1=False,False\n",
    "        v1,v2=set(),set()\n",
    "        def g(i,j):\n",
    "           nonlocal ok,ok1     \n",
    "           if i==n-1 and j==m-1:\n",
    "                if grid[i][j]==1:\n",
    "                    ok,ok1=True,True\n",
    "                return\n",
    "           for a,b in [[0,1],[1,0]]:\n",
    "               x=i+a\n",
    "               y=j+b\n",
    "               if 0<=x<n and 0<=y<m and grid[x][y]==1:\n",
    "                   v1.add((x,y))\n",
    "                   g(x,y)\n",
    "                   if ok:\n",
    "                      return \n",
    "                   v1.remove((x,y))\n",
    "        g(0,0)\n",
    "        ok=False\n",
    "        def g1(i,j):\n",
    "           nonlocal ok \n",
    "           if i==n-1 and j==m-1:\n",
    "               if grid[i][j]==1:\n",
    "                   ok=True\n",
    "           for a,b in [[1,0],[0,1]]:\n",
    "               x=i+a\n",
    "               y=j+b\n",
    "               if 0<=x<n and 0<=y<m and grid[x][y]==1:\n",
    "                   v2.add((x,y))\n",
    "                   g1(x,y)\n",
    "                   if ok:\n",
    "                     return\n",
    "                   v2.remove((x,y))\n",
    "        g1(0,0)           \n",
    "        if not ok1:\n",
    "            print(1) \n",
    "            return  True\n",
    "        for x in v2:\n",
    "          i,j=x[0],x[1]\n",
    "          print(i,j)\n",
    "          if (i*m+j)!=(n-1)*m+m-1 and x in v1:\n",
    "              return True\n",
    "        return False      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        D = [[0] * n for _ in range(m)]\n",
    "        def dfs(i, j):\n",
    "            if i == 0 and j == 0:\n",
    "                return True \n",
    "            flag = 0\n",
    "            for ni, nj in [[i-1, j], [i, j-1]]:\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj]:\n",
    "                    if D[ni][nj]:\n",
    "                        flag = 1\n",
    "                    else:\n",
    "                        D[ni][nj] = 1\n",
    "                        if dfs(ni,nj):\n",
    "                            flag = 1\n",
    "                        else:\n",
    "                            D[ni][nj] = 0 \n",
    "\n",
    "            return flag == 1\n",
    "            \n",
    "        dfs(m-1, n-1)\n",
    "        cnt = [0 ] * (n + m - 1)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if D[i][j] == 1:\n",
    "                    cnt[i + j] += 1\n",
    "        for i in range(1, n+m-2):\n",
    "            if cnt[i] < 2:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        D = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i == 0 and j == 0:\n",
    "                return True \n",
    "            flag = 0\n",
    "            for [ni, nj] in [[i-1, j], [i, j-1]]:\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj]:\n",
    "                    if D[ni][nj]:\n",
    "                        flag = 1\n",
    "                    else:\n",
    "                        D[ni][nj] = 1\n",
    "                        if dfs(ni,nj):\n",
    "                            flag = 1\n",
    "                        else:\n",
    "                            D[ni][nj] = 0 \n",
    "            return flag \n",
    "        \n",
    "        dfs(m-1, n-1)\n",
    "        cnt = [0] * (m + n - 1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if D[i][j] == 1:\n",
    "                    cnt[i + j] += 1\n",
    "        \n",
    "        for i in range(1, m+n-2):\n",
    "            if cnt[i] < 2:\n",
    "                return True \n",
    "        return False "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
